package leetcode

type NumMatrix struct {
	numSum [][]int
}

func Constructor(matrix [][]int) NumMatrix {
	height := len(matrix)
	width := len(matrix[0])
	res := NumMatrix{numSum: make([][]int, height)}
	for i := range res.numSum {
		res.numSum[i] = make([]int, width)
	}

	res.numSum[0][0] = matrix[0][0]
	for j := 1; j < width; j++ {
		res.numSum[0][j] = res.numSum[0][j-1] + matrix[0][j]
	}

	for i := 1; i < height; i++ {
		res.numSum[i][0] = res.numSum[i-1][0] + matrix[i][0]
		for j := 1; j < width; j++ {
			res.numSum[i][j] = res.numSum[i-1][j] + res.numSum[i][j-1] - res.numSum[i-1][j-1] + matrix[i][j]
		}
	}

	return res
}

func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
	if row1 == 0 {
		if col1 == 0 {
			return this.numSum[row2][col2]
		} else {
			return this.numSum[row2][col2] - this.numSum[row2][col1-1]
		}
	} else {
		if col1 == 0 {
			return this.numSum[row2][col2] - this.numSum[row1-1][col2]
		} else {
			return this.numSum[row2][col2] + this.numSum[row1-1][col1-1] - this.numSum[row2][col1-1] - this.numSum[row1-1][col2]
		}
	}
}
